package com.jack.leetcode.eachproblem_2020;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 二叉树的层平均值 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public List<Double> averageOfLevels(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        List<Double> result = new ArrayList<>();
        List<List<Integer>> tmpList = new ArrayList<>();
        dfs(tmpList, root, 0);
        for (List<Integer> integers : tmpList) {
            if(!integers.isEmpty()){
                int sum = 0;
                int count = 0;
                for (Integer integer : integers) {
                    System.out.print(integer+" ");
                    sum += integer;
                    count++;
                }
                System.out.println();
                result.add(sum / (count + 0.0));
            }
        }
        return result;
    }

    private void dfs(List<List<Integer>> result, TreeNode root, int index){
        if(root == null){
            return;
        }
        if(result.size() > index){
            result.get(index).add(root.val);
        }else{
            List<Integer> tmp = new ArrayList<>();
            tmp.add(root.val);
            result.add(tmp);
        }
        dfs(result, root.left, index+1);
        dfs(result, root.right, index+1);
    }
}
